package algorithm.monotonousStack;

public class CountSubmatricesWithAllOnes {

    public static int numSubmat(int[][] mat) {
        int num = 0;
        int[] height = new int[mat[0].length];
        int[] stack = new int[mat[0].length];
        int last = -1;

        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (mat[i][j] == 0)
                    height[j] = 0;
                else
                    height[j]++;
            }
            last = -1;
            for (int j = 0; j < mat[0].length; j++) {
                while (last != -1 && height[stack[last]] >= height[j]) {
                    int pop = stack[last--];
                    if (height[pop] != height[j]) {
                        int start = last == -1? -1 : stack[last];
                        int end = j - 1;
                        int n = end - start;
                        int high = height[pop] - Math.max(start == -1? 0 : height[start], height[end + 1]);
                        num += high * (n + 1) * n / 2;
                    }
                }
                stack[++last] = j;
            }

            while (last != -1) {
                int pop = stack[last--];
                int start = last == -1? -1 : stack[last];
                int end = mat[0].length - 1;
                int n = end - start;
                int high = height[pop] - (start == -1? 0 : height[start]);
                num += high * (n + 1) * n / 2;

            }
        }
        return num;
    }

    public static void main(String[] args) {

    }

}
